package com.wenhai.liuyubobobo.imooc.sort;

import java.util.Arrays;

/**
 * 实现原地选择排序
 * <p>
 * 选择排序：
 * 选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，
 * 存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，
 * 直到全部待排序的数据元素排完。
 *
 * @author wenhai
 * @date 2020/9/9
 */
public class SelectionSort {
    private SelectionSort() {
    }

    public static void main(String[] args) {
        int[] dataSize = {1000, 10000, 100000, 1000000};
        for (int size : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(size, size);
            Integer[] arr2 = Arrays.copyOf(arr, arr.length);
            Integer[] arr3 = Arrays.copyOf(arr, arr.length);
            SortingHelper.sortTest("ShellSort", ShellSort::sort, arr);
            SortingHelper.sortTest("ShellSort2", ShellSort::sort2, arr2);
            SortingHelper.sortTest("ShellSort3", ShellSort::sort3, arr3);

        }


    }


//    public static void sort(int[] arr) {
//        for (int i = 0; i < arr.length - 1; i++) {
//            System.out.println("当前选择排序的开始索引位置：" + i);
//            int minIndex = i;
//            for (int j = i + 1; j < arr.length; j++) {
//                if (arr[minIndex] > arr[j]) {
//                    minIndex = j;
//                }
//            }
//            if (minIndex != i) {
//                System.out.println("当前选择排序的最小元素索引位置：" + minIndex);
//                swap(arr, i, minIndex);
//            }
//        }


    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }

    public static <E extends Comparable<E>> void swap(E[] arr, int descIndex, int targetIndex) {
        E temp = arr[descIndex];
        arr[descIndex] = arr[targetIndex];
        arr[targetIndex] = temp;
    }
}
